//  https://www.luogu.com.cn/problem/P1757

#include<iostream>
#include<vector>
using namespace std;

int n, m, cnt;
const int N = 1010;
int dp[N][N];
typedef pair<int, int> pii;
vector<pii> g[N];


int main()
{
    cin >> m >> n;
    for (int i = 1;i <= n;i++)
    {
        int a, b, c;cin >> a >> b >> c;
        cnt = max(cnt, c);
        g[c].push_back({ a,b });
    }

    for (int i = 1;i <= cnt;i++)
        for (int j = m;j >= 0;j--)
        {
            dp[i][j] = dp[i - 1][j];
            for (auto t : g[i])
            {
                int a = t.first, b = t.second;
                if (j >= a) dp[i][j] = max(dp[i][j], dp[i - 1][j - a] + b);
            }
        }

    cout << dp[cnt][m] << endl;
    return 0;
}